/*

big-number.js

javascript code for arbitrary size/precision numbers.

* this file depends on tom wu's jsbn library:
* http://www-cs-students.stanford.edu/~tjw/jsbn/

* jsbn.js and jsbn2.js must be included before including this file

Copyright (C) 2009, Chris Allert, All rights reserved.

This program is free software; you can redistribute it and/or modify it under 
the terms of the GNU General Public License as published by the Free Software 
Foundation; either version 3 of the License, or (at your option) any later 
version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY 
WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A 
PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with 
this program; if not, write to the Free Software Foundation, Inc., 59 Temple 
Place, Suite 330, Boston, MA 02111-1307 USA

The latest version of this file can be downloaded from
http://thought-patches.sourceforge.net/

*/

// these are utility functions for dealing with big numbers.

function big_fraction_to_repeating (f) { 
	/*
	 * input f is object {
	 * numerator: bigint
	 * denominator: bigint
	 * base: bigint desired number base of result
	 * }
	 *
	 * returns object {
	 * before: array of digits before the point
	 * after: array of non-repeating digits after the point (maybe empty)
	 * repeating: array of repeating digits (maybe empty)
	 * base: pass-through base for convenience
	 * }
	 *
	 * all digits in result are bigints
	 * this is so we can use any number base we want
	 */
	var o = new Object();
	o.base = f.base.clone();

	var before = f.numerator.divide(f.denominator);
	o.before = big_int_to_digits(before, f.base);

	//alert("big_fraction_to_repeating:\n" +
	//		f.numerator + "/" + f.denominator +
	//		" = " + o.before.join('_'));

	// to get the fixed and repeating digits
	// 	until the remainder is zero
	// 	or until we get a remainder we've seen before
	// 		
	// 		multiply last remainder by the base
	// 		and divide it by the denominator
	// 		divide result is next digit
	// 		remainder result is new remainder
	
	var digits = 0;
	o.after = new Array();
	o.repeating = new Array();
	var remainders = new Array();

	remainder = f.numerator.mod(f.denominator);
	remainders[remainder] = digits;

	var r = new Array();
	var n;
	while (remainder.compareTo(BigInteger.ZERO) > 0) {
		n = remainder.multiply(f.base);
		r = n.divideAndRemainder(f.denominator);
		o.after.push(r[0]);
		//alert(remainder + ":" + digits + ":" + n + ":" + r.join(":"));
		remainder = r[1];
		if (null != remainders[remainder]) {
			// it's repeating
			// so everything after the index we remembered
			// the last time we saw this remainder is a 
			// repeating digit
			o.repeating = o.after;
			o.after = new Array();
			// shift all non-repeating digits off the
			// list of repeating digits
			for (var i = 0; i < remainders[remainder]; ++i) {
				o.after.push(o.repeating.shift());
			}
			break;
		}
		// remember where we were when we saw the
		// current remainder
		remainders[remainder] = ++digits;
	}

	return o;
}

function repeating_to_big_fraction (r) { 
	/*
	 * input r is object {
	 * before: digits before the "decimal" point
	 * after: non-repeating digits after the "decimal" point
	 * repeating: repeating-digits
	 * base: number base of repeating "decimal"
	 * }
	 *
	 * returns object {
	 * numerator: bigint numerator
	 * denominator: bigint denominator
	 * base: pass-through base for convenience
	 * }
	 */
	alert("repeating_to_big_fraction not implemented");
}

function big_int_to_digits(num, b) {
	/*
	 * convert bigint n to a list of digits in base b
	 *
	 * returns array of bigints for digits.
	 * this is so we can use any number base, however large
	 */

	/* to convert a number to digits in base b:
	 * repeat while number > 0
	 * 	put number mod base at beginning of list of digits
	 * 	divide number by base
	 */
	var a = new Array();
	n = num.clone();
	var r = new Array;
	while (n.compareTo(BigInteger.ZERO) > 0) {
		r = n.divideAndRemainder(b);
		a.unshift(r[1]);
		n = r[0];
	}
	//if (0 == a.length) { a.push(BigInteger.ZERO.clone()); }
	return a;
}

function new_big_int(s, b) {
	/*
	 * s: string of bigint
	 * b: base to assume while parsing
	 *
	 * returns a bigint for use in other functions here
	 */
	var o = new BigInteger(s, b);
	// this is necessary to get zero to compare to itself right
	o = o.add(BigInteger.ONE);
	o = o.subtract(BigInteger.ONE);
	return o;
}

function big_int_format(n, b, show_zero) {
	var a = big_int_to_digits(n, b);
	return big_int_format_digits(a, show_zero);
}

var big_int_digits_table = new Array();
function init_big_int_digits_table() {
big_int_digits_table["0"] = "0";
big_int_digits_table["1"] = "1";
big_int_digits_table["2"] = "2";
big_int_digits_table["3"] = "3";
big_int_digits_table["4"] = "4";
big_int_digits_table["5"] = "5";
big_int_digits_table["6"] = "6";
big_int_digits_table["7"] = "7";
big_int_digits_table["8"] = "8";
big_int_digits_table["9"] = "9";
big_int_digits_table["10"] = "a";
big_int_digits_table["11"] = "b";
big_int_digits_table["12"] = "c";
big_int_digits_table["13"] = "d";
big_int_digits_table["14"] = "e";
big_int_digits_table["15"] = "f";
big_int_digits_table["16"] = "g";
big_int_digits_table["17"] = "h";
big_int_digits_table["18"] = "i";
big_int_digits_table["19"] = "j";
big_int_digits_table["20"] = "k";
big_int_digits_table["21"] = "l";
big_int_digits_table["22"] = "m";
big_int_digits_table["23"] = "n";
big_int_digits_table["24"] = "o";
big_int_digits_table["25"] = "p";
big_int_digits_table["26"] = "q";
big_int_digits_table["27"] = "r";
big_int_digits_table["28"] = "s";
big_int_digits_table["29"] = "t";
big_int_digits_table["30"] = "u";
big_int_digits_table["31"] = "v";
big_int_digits_table["32"] = "w";
big_int_digits_table["33"] = "x";
big_int_digits_table["34"] = "y";
big_int_digits_table["35"] = "z";
big_int_digits_table["36"] = "A";
big_int_digits_table["37"] = "B";
big_int_digits_table["38"] = "C";
big_int_digits_table["39"] = "D";
big_int_digits_table["40"] = "E";
big_int_digits_table["41"] = "F";
big_int_digits_table["42"] = "G";
big_int_digits_table["43"] = "H";
big_int_digits_table["44"] = "I";
big_int_digits_table["45"] = "J";
big_int_digits_table["46"] = "K";
big_int_digits_table["47"] = "L";
big_int_digits_table["48"] = "M";
big_int_digits_table["49"] = "N";
big_int_digits_table["50"] = "O";
big_int_digits_table["51"] = "P";
big_int_digits_table["52"] = "Q";
big_int_digits_table["53"] = "R";
big_int_digits_table["54"] = "S";
big_int_digits_table["55"] = "T";
big_int_digits_table["56"] = "U";
big_int_digits_table["57"] = "V";
big_int_digits_table["58"] = "W";
big_int_digits_table["59"] = "X";
big_int_digits_table["60"] = "Y";
big_int_digits_table["61"] = "Z";
}

init_big_int_digits_table();

function big_int_format_digits(a, show_zero) {

	if (show_zero) {
		if (0 == a.length) {
			return "0";
		}
	}

	var o = "";
	for (var i in a) {
		var d = big_int_digits_table["" + a[i]];
		o += ((null == d) ? ("[" + a[i] + "]") : d);
	}
	return o;
}

